package com.binarytree;

public class Solution29 {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode res = root;
        TreeNode pre = root;
        while (root != null) {
            pre = root;
            if (root.val > val) {
                root = root.left;
            } else if (root.val < val) {
                root = root.right;
            }
        }
        if (val < pre.val)  pre.left = new TreeNode(val);
        else pre.right = new TreeNode(val);
        return res;
    }
}
